import java.util.List;

public class ReverseList {

    public static void main(String[] args) {
        Node node1 = new Node(1, null);
        Node node2 = new Node(2, node1);
        Node node3 = new Node(3, node2);
        Node node4 = new Node(4, node3);
        Node node5 = new Node(5, node4);
        print(node5);
        reverse(node5);
        print(node1);


    }

    /**
     * 递归反转链表
     */
    public static Node reverse(Node list){
        if (list == null || list.next == null){
            return list;
        }
        Node last = reverse(list.next);
        list.next.next = list;
        list.next = null;
        return last;
    }

    public static void print(Node list){
        Node p = list;
        while (p != null){
            System.out.print(p.value);
            p = p.next;
        }
        System.out.println();
    }

    private static class Node{
        int value;
        Node next;

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
}
